/**
 * @file
 * MIB tree access/construction functions.
 */

/*
 * Copyright (c) 2006 Axon Digital Design B.V., The Netherlands.
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without modification,
 * are permitted provided that the following conditions are met:
 *
 * 1. Redistributions of source code must retain the above copyright notice,
 *    this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright notice,
 *    this list of conditions and the following disclaimer in the documentation
 *    and/or other materials provided with the distribution.
 * 3. The name of the author may not be used to endorse or promote products
 *    derived from this software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR IMPLIED
 * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
 * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT
 * SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT
 * OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING
 * IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY
 * OF SUCH DAMAGE.
 *
 * Author: Christiaan Simons <christiaan.simons@axon.tv>
 */

#include "lwip/opt.h"

#if LWIP_SNMP /* don't build if not configured for use in lwipopts.h */

#include "lwip/snmp_structs.h"
#include "lwip/memp.h"
#include "lwip/netif.h"

/** .iso.org.dod.internet address prefix, @see snmp_iso_*() */
const s32_t prefix[4] = {1, 3, 6, 1};

#define NODE_STACK_SIZE (LWIP_SNMP_OBJ_ID_LEN)
/** node stack entry (old news?) */
struct nse {
	/** right child */
	struct mib_node *r_ptr;
	/** right child identifier */
	s32_t r_id;
	/** right child next level */
	u8_t r_nl;
};
static u8_t       node_stack_cnt;
static struct nse node_stack[NODE_STACK_SIZE];

/**
 * Pushes nse struct onto stack.
 */
static void push_node(struct nse *node)
{
	LWIP_ASSERT("node_stack_cnt < NODE_STACK_SIZE", node_stack_cnt < NODE_STACK_SIZE);
	LWIP_DEBUGF(SNMP_MIB_DEBUG, ("push_node() node=%p id=%" S32_F "\n", (void *)(node->r_ptr), node->r_id));
	if (node_stack_cnt < NODE_STACK_SIZE) {
		node_stack[node_stack_cnt] = *node;
		node_stack_cnt++;
	}
}

/**
 * Pops nse struct from stack.
 */
static void pop_node(struct nse *node)
{
	if (node_stack_cnt > 0) {
		node_stack_cnt--;
		*node = node_stack[node_stack_cnt];
	}
	LWIP_DEBUGF(SNMP_MIB_DEBUG, ("pop_node() node=%p id=%" S32_F "\n", (void *)(node->r_ptr), node->r_id));
}

/**
 * Conversion from ifIndex to lwIP netif
 * @param ifindex is a s32_t object sub-identifier
 * @param netif points to returned netif struct pointer
 */
void snmp_ifindextonetif(s32_t ifindex, struct netif **netif)
{
	struct netif *nif = netif_list;
	s32_t         i, ifidx;

	ifidx = ifindex - 1;
	i     = 0;
	while ((nif != NULL) && (i < ifidx)) {
		nif = nif->next;
		i++;
	}
	*netif = nif;
}

/**
 * Conversion from lwIP netif to ifIndex
 * @param netif points to a netif struct
 * @param ifidx points to s32_t object sub-identifier
 */
void snmp_netiftoifindex(struct netif *netif, s32_t *ifidx)
{
	struct netif *nif = netif_list;
	u16_t         i;

	i = 0;
	while ((nif != NULL) && (nif != netif)) {
		nif = nif->next;
		i++;
	}
	*ifidx = i + 1;
}

/**
 * Conversion from oid to lwIP ip_addr
 * @param ident points to s32_t ident[4] input
 * @param ip points to output struct
 */
void snmp_oidtoip(s32_t *ident, ip_addr_t *ip)
{
	IP4_ADDR(ip, ident[0], ident[1], ident[2], ident[3]);
}

/**
 * Conversion from lwIP ip_addr to oid
 * @param ip points to input struct
 * @param ident points to s32_t ident[4] output
 */
void snmp_iptooid(ip_addr_t *ip, s32_t *ident)
{
	ident[0] = ip4_addr1(ip);
	ident[1] = ip4_addr2(ip);
	ident[2] = ip4_addr3(ip);
	ident[3] = ip4_addr4(ip);
}

struct mib_list_node *snmp_mib_ln_alloc(s32_t id)
{
	struct mib_list_node *ln;

	ln = (struct mib_list_node *)memp_malloc(MEMP_SNMP_NODE);
	if (ln != NULL) {
		ln->prev  = NULL;
		ln->next  = NULL;
		ln->objid = id;
		ln->nptr  = NULL;
	}
	return ln;
}

void snmp_mib_ln_free(struct mib_list_node *ln)
{
	memp_free(MEMP_SNMP_NODE, ln);
}

struct mib_list_rootnode *snmp_mib_lrn_alloc(void)
{
	struct mib_list_rootnode *lrn;

	lrn = (struct mib_list_rootnode *)memp_malloc(MEMP_SNMP_ROOTNODE);
	if (lrn != NULL) {
		lrn->get_object_def = noleafs_get_object_def;
		lrn->get_value      = noleafs_get_value;
		lrn->set_test       = noleafs_set_test;
		lrn->set_value      = noleafs_set_value;
		lrn->node_type      = MIB_NODE_LR;
		lrn->maxlength      = 0;
		lrn->head           = NULL;
		lrn->tail           = NULL;
		lrn->count          = 0;
	}
	return lrn;
}

void snmp_mib_lrn_free(struct mib_list_rootnode *lrn)
{
	memp_free(MEMP_SNMP_ROOTNODE, lrn);
}

/**
 * Inserts node in idx list in a sorted
 * (ascending order) fashion and
 * allocates the node if needed.
 *
 * @param rn points to the root node
 * @param objid is the object sub identifier
 * @param insn points to a pointer to the inserted node
 *   used for constructing the tree.
 * @return -1 if failed, 1 if inserted, 2 if present.
 */
s8_t snmp_mib_node_insert(struct mib_list_rootnode *rn, s32_t objid, struct mib_list_node **insn)
{
	struct mib_list_node *nn;
	s8_t                  insert;

	LWIP_ASSERT("rn != NULL", rn != NULL);

	/* -1 = malloc failure, 0 = not inserted, 1 = inserted, 2 = was present */
	insert = 0;
	if (rn->head == NULL) {
		/* empty list, add first node */
		LWIP_DEBUGF(SNMP_MIB_DEBUG, ("alloc empty list objid==%" S32_F "\n", objid));
		nn = snmp_mib_ln_alloc(objid);
		if (nn != NULL) {
			rn->head = nn;
			rn->tail = nn;
			*insn    = nn;
			insert   = 1;
		} else {
			insert = -1;
		}
	} else {
		struct mib_list_node *n;
		/* at least one node is present */
		n = rn->head;
		while ((n != NULL) && (insert == 0)) {
			if (n->objid == objid) {
				/* node is already there */
				LWIP_DEBUGF(SNMP_MIB_DEBUG, ("node already there objid==%" S32_F "\n", objid));
				*insn  = n;
				insert = 2;
			} else if (n->objid < objid) {
				if (n->next == NULL) {
					/* alloc and insert at the tail */
					LWIP_DEBUGF(SNMP_MIB_DEBUG, ("alloc ins tail objid==%" S32_F "\n", objid));
					nn = snmp_mib_ln_alloc(objid);
					if (nn != NULL) {
						nn->next = NULL;
						nn->prev = n;
						n->next  = nn;
						rn->tail = nn;
						*insn    = nn;
						insert   = 1;
					} else {
						/* insertion failure */
						insert = -1;
					}
				} else {
					/* there's more to explore: traverse list */
					LWIP_DEBUGF(SNMP_MIB_DEBUG, ("traverse list\n"));
					n = n->next;
				}
			} else {
				/* n->objid > objid */
				/* alloc and insert between n->prev and n */
				LWIP_DEBUGF(SNMP_MIB_DEBUG, ("alloc ins n->prev, objid==%" S32_F ", n\n", objid));
				nn = snmp_mib_ln_alloc(objid);
				if (nn != NULL) {
					if (n->prev == NULL) {
						/* insert at the head */
						nn->next = n;
						nn->prev = NULL;
						rn->head = nn;
						n->prev  = nn;
					} else {
						/* insert in the middle */
						nn->next      = n;
						nn->prev      = n->prev;
						n->prev->next = nn;
						n->prev       = nn;
					}
					*insn  = nn;
					insert = 1;
				} else {
					/* insertion failure */
					insert = -1;
				}
			}
		}
	}
	if (insert == 1) {
		rn->count += 1;
	}
	LWIP_ASSERT("insert != 0", insert != 0);
	return insert;
}

/**
 * Finds node in idx list and returns deletion mark.
 *
 * @param rn points to the root node
 * @param objid  is the object sub identifier
 * @param fn returns pointer to found node
 * @return 0 if not found, 1 if deletable,
 *   2 can't delete (2 or more children), 3 not a list_node
 */
s8_t snmp_mib_node_find(struct mib_list_rootnode *rn, s32_t objid, struct mib_list_node **fn)
{
	s8_t                  fc;
	struct mib_list_node *n;

	LWIP_ASSERT("rn != NULL", rn != NULL);
	n = rn->head;
	while ((n != NULL) && (n->objid != objid)) {
		n = n->next;
	}
	if (n == NULL) {
		fc = 0;
	} else if (n->nptr == NULL) {
		/* leaf, can delete node */
		fc = 1;
	} else {
		struct mib_list_rootnode *r;

		if (n->nptr->node_type == MIB_NODE_LR) {
			r = (struct mib_list_rootnode *)n->nptr;
			if (r->count > 1) {
				/* can't delete node */
				fc = 2;
			} else {
				/* count <= 1, can delete node */
				fc = 1;
			}
		} else {
			/* other node type */
			fc = 3;
		}
	}
	*fn = n;
	return fc;
}

/**
 * Removes node from idx list
 * if it has a single child left.
 *
 * @param rn points to the root node
 * @param n points to the node to delete
 * @return the nptr to be freed by caller
 */
struct mib_list_rootnode *snmp_mib_node_delete(struct mib_list_rootnode *rn, struct mib_list_node *n)
{
	struct mib_list_rootnode *next;

	LWIP_ASSERT("rn != NULL", rn != NULL);
	LWIP_ASSERT("n != NULL", n != NULL);

	/* caller must remove this sub-tree */
	next = (struct mib_list_rootnode *)(n->nptr);
	rn->count -= 1;

	if (n == rn->head) {
		rn->head = n->next;
		if (n->next != NULL) {
			/* not last node, new list begin */
			n->next->prev = NULL;
		}
	} else if (n == rn->tail) {
		rn->tail = n->prev;
		if (n->prev != NULL) {
			/* not last node, new list end */
			n->prev->next = NULL;
		}
	} else {
		/* node must be in the middle */
		n->prev->next = n->next;
		n->next->prev = n->prev;
	}
	LWIP_DEBUGF(SNMP_MIB_DEBUG, ("free list objid==%" S32_F "\n", n->objid));
	snmp_mib_ln_free(n);
	if (rn->count == 0) {
		rn->head = NULL;
		rn->tail = NULL;
	}
	return next;
}

/**
 * Searches tree for the supplied (scalar?) object identifier.
 *
 * @param node points to the root of the tree ('.internet')
 * @param ident_len the length of the supplied object identifier
 * @param ident points to the array of sub identifiers
 * @param np points to the found object instance (return)
 * @return pointer to the requested parent (!) node if success, NULL otherwise
 */
struct mib_node *snmp_search_tree(struct mib_node *node, u8_t ident_len, s32_t *ident, struct snmp_name_ptr *np)
{
	u8_t node_type, ext_level;

	ext_level = 0;
	LWIP_DEBUGF(SNMP_MIB_DEBUG, ("node==%p *ident==%" S32_F "\n", (void *)node, *ident));
	while (node != NULL) {
		node_type = node->node_type;
		if ((node_type == MIB_NODE_AR) || (node_type == MIB_NODE_RA)) {
			struct mib_array_node *an;
			u16_t                  i;

			if (ident_len > 0) {
				/* array node (internal ROM or RAM, fixed length) */
				an = (struct mib_array_node *)node;
				i  = 0;
				while ((i < an->maxlength) && (an->objid[i] != *ident)) {
					i++;
				}
				if (i < an->maxlength) {
					/* found it, if available proceed to child, otherwise inspect leaf */
					LWIP_DEBUGF(SNMP_MIB_DEBUG,
					            ("an->objid[%" U16_F "]==%" S32_F " *ident==%" S32_F "\n", i, an->objid[i], *ident));
					if (an->nptr[i] == NULL) {
						/* a scalar leaf OR table,
						   inspect remaining instance number / table index */
						np->ident_len = ident_len;
						np->ident     = ident;
						return (struct mib_node *)an;
					} else {
						/* follow next child pointer */
						ident++;
						ident_len--;
						node = an->nptr[i];
					}
				} else {
					/* search failed, identifier mismatch (nosuchname) */
					LWIP_DEBUGF(SNMP_MIB_DEBUG, ("an search failed *ident==%" S32_F "\n", *ident));
					return NULL;
				}
			} else {
				/* search failed, short object identifier (nosuchname) */
				LWIP_DEBUGF(SNMP_MIB_DEBUG, ("an search failed, short object identifier\n"));
				return NULL;
			}
		} else if (node_type == MIB_NODE_LR) {
			struct mib_list_rootnode *lrn;
			struct mib_list_node *    ln;

			if (ident_len > 0) {
				/* list root node (internal 'RAM', variable length) */
				lrn = (struct mib_list_rootnode *)node;
				ln  = lrn->head;
				/* iterate over list, head to tail */
				while ((ln != NULL) && (ln->objid != *ident)) {
					ln = ln->next;
				}
				if (ln != NULL) {
					/* found it, proceed to child */;
					LWIP_DEBUGF(SNMP_MIB_DEBUG, ("ln->objid==%" S32_F " *ident==%" S32_F "\n", ln->objid, *ident));
					if (ln->nptr == NULL) {
						np->ident_len = ident_len;
						np->ident     = ident;
						return (struct mib_node *)lrn;
					} else {
						/* follow next child pointer */
						ident_len--;
						ident++;
						node = ln->nptr;
					}
				} else {
					/* search failed */
					LWIP_DEBUGF(SNMP_MIB_DEBUG, ("ln search failed *ident==%" S32_F "\n", *ident));
					return NULL;
				}
			} else {
				/* search failed, short object identifier (nosuchname) */
				LWIP_DEBUGF(SNMP_MIB_DEBUG, ("ln search failed, short object identifier\n"));
				return NULL;
			}
		} else if (node_type == MIB_NODE_EX) {
			struct mib_external_node *en;
			u16_t                     i, len;

			if (ident_len > 0) {
				/* external node (addressing and access via functions) */
				en = (struct mib_external_node *)node;

				i   = 0;
				len = en->level_length(en->addr_inf, ext_level);
				while ((i < len) && (en->ident_cmp(en->addr_inf, ext_level, i, *ident) != 0)) {
					i++;
				}
				if (i < len) {
					s32_t debug_id;

					en->get_objid(en->addr_inf, ext_level, i, &debug_id);
					LWIP_DEBUGF(SNMP_MIB_DEBUG, ("en->objid==%" S32_F " *ident==%" S32_F "\n", debug_id, *ident));
					if ((ext_level + 1) == en->tree_levels) {
						np->ident_len = ident_len;
						np->ident     = ident;
						return (struct mib_node *)en;
					} else {
						/* found it, proceed to child */
						ident_len--;
						ident++;
						ext_level++;
					}
				} else {
					/* search failed */
					LWIP_DEBUGF(SNMP_MIB_DEBUG, ("en search failed *ident==%" S32_F "\n", *ident));
					return NULL;
				}
			} else {
				/* search failed, short object identifier (nosuchname) */
				LWIP_DEBUGF(SNMP_MIB_DEBUG, ("en search failed, short object identifier\n"));
				return NULL;
			}
		} else if (node_type == MIB_NODE_SC) {
			mib_scalar_node *sn;

			sn = (mib_scalar_node *)node;
			if ((ident_len == 1) && (*ident == 0)) {
				np->ident_len = ident_len;
				np->ident     = ident;
				return (struct mib_node *)sn;
			} else {
				/* search failed, short object identifier (nosuchname) */
				LWIP_DEBUGF(SNMP_MIB_DEBUG, ("search failed, invalid object identifier length\n"));
				return NULL;
			}
		} else {
			/* unknown node_type */
			LWIP_DEBUGF(SNMP_MIB_DEBUG, ("search failed node_type %" U16_F " unkown\n", (u16_t)node_type));
			return NULL;
		}
	}
	/* done, found nothing */
	LWIP_DEBUGF(SNMP_MIB_DEBUG, ("search failed node==%p\n", (void *)node));
	return NULL;
}

/**
 * Test table for presence of at least one table entry.
 */
static u8_t empty_table(struct mib_node *node)
{
	u8_t node_type;
	u8_t empty = 0;

	if (node != NULL) {
		node_type = node->node_type;
		if (node_type == MIB_NODE_LR) {
			struct mib_list_rootnode *lrn;
			lrn = (struct mib_list_rootnode *)node;
			if ((lrn->count == 0) || (lrn->head == NULL)) {
				empty = 1;
			}
		} else if ((node_type == MIB_NODE_AR) || (node_type == MIB_NODE_RA)) {
			struct mib_array_node *an;
			an = (struct mib_array_node *)node;
			if ((an->maxlength == 0) || (an->nptr == NULL)) {
				empty = 1;
			}
		} else if (node_type == MIB_NODE_EX) {
			struct mib_external_node *en;
			en = (struct mib_external_node *)node;
			if (en->tree_levels == 0) {
				empty = 1;
			}
		}
	}
	return empty;
}

/**
 * Tree expansion.
 */
struct mib_node *snmp_expand_tree(struct mib_node *node, u8_t ident_len, s32_t *ident, struct snmp_obj_id *oidret)
{
	u8_t node_type, ext_level, climb_tree;

	ext_level = 0;
	/* reset node stack */
	node_stack_cnt = 0;
	while (node != NULL) {
		climb_tree = 0;
		node_type  = node->node_type;
		if ((node_type == MIB_NODE_AR) || (node_type == MIB_NODE_RA)) {
			struct mib_array_node *an;
			u16_t                  i;

			/* array node (internal ROM or RAM, fixed length) */
			an = (struct mib_array_node *)node;
			if (ident_len > 0) {
				i = 0;
				while ((i < an->maxlength) && (an->objid[i] < *ident)) {
					i++;
				}
				if (i < an->maxlength) {
					LWIP_DEBUGF(SNMP_MIB_DEBUG,
					            ("an->objid[%" U16_F "]==%" S32_F " *ident==%" S32_F "\n", i, an->objid[i], *ident));
					/* add identifier to oidret */
					oidret->id[oidret->len] = an->objid[i];
					(oidret->len)++;

					if (an->nptr[i] == NULL) {
						LWIP_DEBUGF(SNMP_MIB_DEBUG, ("leaf node\n"));
						/* leaf node (e.g. in a fixed size table) */
						if (an->objid[i] > *ident) {
							return (struct mib_node *)an;
						} else if ((i + 1) < an->maxlength) {
							/* an->objid[i] == *ident */
							(oidret->len)--;
							oidret->id[oidret->len] = an->objid[i + 1];
							(oidret->len)++;
							return (struct mib_node *)an;
						} else {
							/* (i + 1) == an->maxlength */
							(oidret->len)--;
							climb_tree = 1;
						}
					} else {
						u8_t       j;
						struct nse cur_node;

						LWIP_DEBUGF(SNMP_MIB_DEBUG, ("non-leaf node\n"));
						/* non-leaf, store right child ptr and id */
						LWIP_ASSERT("i < 0xff", i < 0xff);
						j = (u8_t)i + 1;
						while ((j < an->maxlength) && (empty_table(an->nptr[j]))) {
							j++;
						}
						if (j < an->maxlength) {
							cur_node.r_ptr = an->nptr[j];
							cur_node.r_id  = an->objid[j];
							cur_node.r_nl  = 0;
						} else {
							cur_node.r_ptr = NULL;
						}
						push_node(&cur_node);
						if (an->objid[i] == *ident) {
							ident_len--;
							ident++;
						} else {
							/* an->objid[i] < *ident */
							ident_len = 0;
						}
						/* follow next child pointer */
						node = an->nptr[i];
					}
				} else {
					/* i == an->maxlength */
					climb_tree = 1;
				}
			} else {
				u8_t j;
				/* ident_len == 0, complete with leftmost '.thing' */
				j = 0;
				while ((j < an->maxlength) && empty_table(an->nptr[j])) {
					j++;
				}
				if (j < an->maxlength) {
					LWIP_DEBUGF(SNMP_MIB_DEBUG, ("left an->objid[j]==%" S32_F "\n", an->objid[j]));
					oidret->id[oidret->len] = an->objid[j];
					(oidret->len)++;
					if (an->nptr[j] == NULL) {
						/* leaf node */
						return (struct mib_node *)an;
					} else {
						/* no leaf, continue */
						node = an->nptr[j];
					}
				} else {
					/* j == an->maxlength */
					climb_tree = 1;
				}
			}
		} else if (node_type == MIB_NODE_LR) {
			struct mib_list_rootnode *lrn;
			struct mib_list_node *    ln;

			/* list root node (internal 'RAM', variable length) */
			lrn = (struct mib_list_rootnode *)node;
			if (ident_len > 0) {
				ln = lrn->head;
				/* iterate over list, head to tail */
				while ((ln != NULL) && (ln->objid < *ident)) {
					ln = ln->next;
				}
				if (ln != NULL) {
					LWIP_DEBUGF(SNMP_MIB_DEBUG, ("ln->objid==%" S32_F " *ident==%" S32_F "\n", ln->objid, *ident));
					oidret->id[oidret->len] = ln->objid;
					(oidret->len)++;
					if (ln->nptr == NULL) {
						/* leaf node */
						if (ln->objid > *ident) {
							return (struct mib_node *)lrn;
						} else if (ln->next != NULL) {
							/* ln->objid == *ident */
							(oidret->len)--;
							oidret->id[oidret->len] = ln->next->objid;
							(oidret->len)++;
							return (struct mib_node *)lrn;
						} else {
							/* ln->next == NULL */
							(oidret->len)--;
							climb_tree = 1;
						}
					} else {
						struct mib_list_node *jn;
						struct nse            cur_node;

						/* non-leaf, store right child ptr and id */
						jn = ln->next;
						while ((jn != NULL) && empty_table(jn->nptr)) {
							jn = jn->next;
						}
						if (jn != NULL) {
							cur_node.r_ptr = jn->nptr;
							cur_node.r_id  = jn->objid;
							cur_node.r_nl  = 0;
						} else {
							cur_node.r_ptr = NULL;
						}
						push_node(&cur_node);
						if (ln->objid == *ident) {
							ident_len--;
							ident++;
						} else {
							/* ln->objid < *ident */
							ident_len = 0;
						}
						/* follow next child pointer */
						node = ln->nptr;
					}

				} else {
					/* ln == NULL */
					climb_tree = 1;
				}
			} else {
				struct mib_list_node *jn;
				/* ident_len == 0, complete with leftmost '.thing' */
				jn = lrn->head;
				while ((jn != NULL) && empty_table(jn->nptr)) {
					jn = jn->next;
				}
				if (jn != NULL) {
					LWIP_DEBUGF(SNMP_MIB_DEBUG, ("left jn->objid==%" S32_F "\n", jn->objid));
					oidret->id[oidret->len] = jn->objid;
					(oidret->len)++;
					if (jn->nptr == NULL) {
						/* leaf node */
						LWIP_DEBUGF(SNMP_MIB_DEBUG, ("jn->nptr == NULL\n"));
						return (struct mib_node *)lrn;
					} else {
						/* no leaf, continue */
						node = jn->nptr;
					}
				} else {
					/* jn == NULL */
					climb_tree = 1;
				}
			}
		} else if (node_type == MIB_NODE_EX) {
			struct mib_external_node *en;
			s32_t                     ex_id;

			/* external node (addressing and access via functions) */
			en = (struct mib_external_node *)node;
			if (ident_len > 0) {
				u16_t i, len;

				i   = 0;
				len = en->level_length(en->addr_inf, ext_level);
				while ((i < len) && (en->ident_cmp(en->addr_inf, ext_level, i, *ident) < 0)) {
					i++;
				}
				if (i < len) {
					/* add identifier to oidret */
					en->get_objid(en->addr_inf, ext_level, i, &ex_id);
					LWIP_DEBUGF(SNMP_MIB_DEBUG,
					            ("en->objid[%" U16_F "]==%" S32_F " *ident==%" S32_F "\n", i, ex_id, *ident));
					oidret->id[oidret->len] = ex_id;
					(oidret->len)++;

					if ((ext_level + 1) == en->tree_levels) {
						LWIP_DEBUGF(SNMP_MIB_DEBUG, ("leaf node\n"));
						/* leaf node */
						if (ex_id > *ident) {
							return (struct mib_node *)en;
						} else if ((i + 1) < len) {
							/* ex_id == *ident */
							en->get_objid(en->addr_inf, ext_level, i + 1, &ex_id);
							(oidret->len)--;
							oidret->id[oidret->len] = ex_id;
							(oidret->len)++;
							return (struct mib_node *)en;
						} else {
							/* (i + 1) == len */
							(oidret->len)--;
							climb_tree = 1;
						}
					} else {
						u8_t       j;
						struct nse cur_node;

						LWIP_DEBUGF(SNMP_MIB_DEBUG, ("non-leaf node\n"));
						/* non-leaf, store right child ptr and id */
						LWIP_ASSERT("i < 0xff", i < 0xff);
						j = (u8_t)i + 1;
						if (j < len) {
							/* right node is the current external node */
							cur_node.r_ptr = node;
							en->get_objid(en->addr_inf, ext_level, j, &cur_node.r_id);
							cur_node.r_nl = ext_level + 1;
						} else {
							cur_node.r_ptr = NULL;
						}
						push_node(&cur_node);
						if (en->ident_cmp(en->addr_inf, ext_level, i, *ident) == 0) {
							ident_len--;
							ident++;
						} else {
							/* external id < *ident */
							ident_len = 0;
						}
						/* proceed to child */
						ext_level++;
					}
				} else {
					/* i == len (en->level_len()) */
					climb_tree = 1;
				}
			} else {
				/* ident_len == 0, complete with leftmost '.thing' */
				en->get_objid(en->addr_inf, ext_level, 0, &ex_id);
				LWIP_DEBUGF(SNMP_MIB_DEBUG, ("left en->objid==%" S32_F "\n", ex_id));
				oidret->id[oidret->len] = ex_id;
				(oidret->len)++;
				if ((ext_level + 1) == en->tree_levels) {
					/* leaf node */
					LWIP_DEBUGF(SNMP_MIB_DEBUG, ("(ext_level + 1) == en->tree_levels\n"));
					return (struct mib_node *)en;
				} else {
					/* no leaf, proceed to child */
					ext_level++;
				}
			}
		} else if (node_type == MIB_NODE_SC) {
			mib_scalar_node *sn;

			/* scalar node  */
			sn = (mib_scalar_node *)node;
			if (ident_len > 0) {
				/* at .0 */
				climb_tree = 1;
			} else {
				/* ident_len == 0, complete object identifier */
				oidret->id[oidret->len] = 0;
				(oidret->len)++;
				/* leaf node */
				LWIP_DEBUGF(SNMP_MIB_DEBUG, ("completed scalar leaf\n"));
				return (struct mib_node *)sn;
			}
		} else {
			/* unknown/unhandled node_type */
			LWIP_DEBUGF(SNMP_MIB_DEBUG, ("expand failed node_type %" U16_F " unkown\n", (u16_t)node_type));
			return NULL;
		}

		if (climb_tree) {
			struct nse child;

			/* find right child ptr */
			child.r_ptr = NULL;
			child.r_id  = 0;
			child.r_nl  = 0;
			while ((node_stack_cnt > 0) && (child.r_ptr == NULL)) {
				pop_node(&child);
				/* trim returned oid */
				(oidret->len)--;
			}
			if (child.r_ptr != NULL) {
				/* incoming ident is useless beyond this point */
				ident_len               = 0;
				oidret->id[oidret->len] = child.r_id;
				oidret->len++;
				node      = child.r_ptr;
				ext_level = child.r_nl;
			} else {
				/* tree ends here ... */
				LWIP_DEBUGF(SNMP_MIB_DEBUG, ("expand failed, tree ends here\n"));
				return NULL;
			}
		}
	}
	/* done, found nothing */
	LWIP_DEBUGF(SNMP_MIB_DEBUG, ("expand failed node==%p\n", (void *)node));
	return NULL;
}

/**
 * Test object identifier for the iso.org.dod.internet prefix.
 *
 * @param ident_len the length of the supplied object identifier
 * @param ident points to the array of sub identifiers
 * @return 1 if it matches, 0 otherwise
 */
u8_t snmp_iso_prefix_tst(u8_t ident_len, s32_t *ident)
{
	if ((ident_len > 3) && (ident[0] == 1) && (ident[1] == 3) && (ident[2] == 6) && (ident[3] == 1)) {
		return 1;
	} else {
		return 0;
	}
}

/**
 * Expands object identifier to the iso.org.dod.internet
 * prefix for use in getnext operation.
 *
 * @param ident_len the length of the supplied object identifier
 * @param ident points to the array of sub identifiers
 * @param oidret points to returned expanded object identifier
 * @return 1 if it matches, 0 otherwise
 *
 * @note ident_len 0 is allowed, expanding to the first known object id!!
 */
u8_t snmp_iso_prefix_expand(u8_t ident_len, s32_t *ident, struct snmp_obj_id *oidret)
{
	const s32_t *prefix_ptr;
	s32_t *      ret_ptr;
	u8_t         i;

	i          = 0;
	prefix_ptr = &prefix[0];
	ret_ptr    = &oidret->id[0];
	ident_len  = ((ident_len < 4) ? ident_len : 4);
	while ((i < ident_len) && ((*ident) <= (*prefix_ptr))) {
		*ret_ptr++ = *prefix_ptr++;
		ident++;
		i++;
	}
	if (i == ident_len) {
		/* match, complete missing bits */
		while (i < 4) {
			*ret_ptr++ = *prefix_ptr++;
			i++;
		}
		oidret->len = i;
		return 1;
	} else {
		/* i != ident_len */
		return 0;
	}
}

#endif /* LWIP_SNMP */
